#
# @lc app=leetcode.cn id=516 lang=python3
#
# [516] 最长回文子序列
#

# @lc code=start
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        # dp[i][j]表示s[i...j]最长回文子序列的长度
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i]=1 # 单个字符串也是回文串
        # i从右往左循环
        for i in range(n-1, -1, -1): # [0, n-1]
            # dp[i][j]=1
            # j从左往右循环
            for j in range(i+1, n): # [i+1, n-1]
                if s[i]==s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    # 注意遍历顺序，i 从最后一个字符开始往前遍历，
                    # j 从 i + 1 开始往后遍历，这样可以保证每个子问题都已经算好了。
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        
        return dp[0][n-1]
            
# @lc code=end

